import collections
class Solution(object):
    def minimumDifference(self, nums):
        n = len(nums) // 2
        t_sum = sum(nums)
        mid_sum = t_sum / 2
        nums1 = nums[:n]
        nums2 = nums[n:]
        d1 = collections.defaultdict(set)
        d2 = collections.defaultdict(set)
        def dfs_1(i, val, count):
            if i == n:
                d1[count].add(val)
            else:
                dfs_1(i + 1, val, count)
                val += nums1[i]
                count += 1
                dfs_1(i + 1, val, count)
            
        def dfs_2(i, val, count):
            if i == n:
                d2[count].add(val)
            else:
                dfs_2(i + 1, val, count)
                val += nums2[i]
                count += 1
                dfs_2(i + 1, val, count)
        dfs_1(0, 0, 0)
        dfs_2(0, 0, 0)
        ans = float('inf')
        for i in range(n + 1):
            l1 = list(d1[i])
            l2 = list(d2[n - i])
            m1 = len(l1)
            m2 = len(l2)
            l1.sort()
            l2.sort()
            index1 = 0
            index2 = m2 - 1
            while index1 < m1 and index2 >= 0:
                val = l1[index1] + l2[index2] 
                ans = min(ans, abs(t_sum - 2 * val))
                if val >= mid_sum:
                    index2 -= 1
                else:
                    index1 += 1
        return ans




data = Solution()
nums = [-36,36]
print(data.minimumDifference(nums))